﻿#pragma once
/*
给你一个字符串 s，找到 s 中最长的
回文

子串
。



示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"

*/




#include <string>
#include <vector>
using namespace std;
namespace Solution
{
	/*
	   动态规划方法: 递推
	   P(i,j) = P(i+1,j−1)∧(Si == Sj)
	   也就是说，只有 s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串
	   我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；
	   对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
	   {P(i,i)=true, P(i,i+1)=(Si == Si+1)}
	*/
	class Solution1 {
	public:
		string longestPalindrome(string s) {
			int n = s.size();
			if (n < 2) {
				return s;
			}

			int maxLen = 1;
			int begin = 0;
			// dp[i][j] 表示 s[i..j] 是否是回文串
			vector<vector<int>> dp(n, vector<int>(n));
			// 初始化：所有长度为 1 的子串都是回文串
			for (int i = 0; i < n; i++) {
				dp[i][i] = true;
			}
			// 递推开始
			// 先枚举子串长度
			for (int L = 2; L <= n; L++) {
				// 枚举左边界，左边界的上限设置可以宽松一些
				for (int i = 0; i < n; i++) {
					// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
					int j = L + i - 1;
					// 如果右边界越界，就可以退出当前循环
					if (j >= n) {
						break;
					}

					if (s[i] != s[j]) {
						dp[i][j] = false;
					}
					else {
						if (j - i < 3) {
							dp[i][j] = true;
						}
						else {
							dp[i][j] = dp[i + 1][j - 1];
						}
					}

					// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
					if (dp[i][j] && j - i + 1 > maxLen) {
						maxLen = j - i + 1;
						begin = i;
					}
				}
			}
			return s.substr(begin, maxLen);
		}
	};
}
